In Internet Protocol Version 6 (IPv6), techniques are introduced for network elements to discover the presence of other network elements on the same link and corresponding attributes for those network elements. This protocol, known as Neighbor Discovery (ND) for IPv6 (IPv6 ND), enables a network element to discover IPv6 addresses and link layer addresses of its neighbor network elements. Furthermore, techniques introduced in conjunction with IPv6 ND allow a network element to autoconfigure an IP address on an interface and perform Duplicate Address Detection (DAD) prior to utilizing that IP address on the network. The DAD procedure ensures that the autoconfigured IP address is unique, not utilized by another interface on the network.
As described in the Internet Engineering Task Force (IETF) standards track Request for Comments (RFC) Neighbor Discovery for IP version 6 (IPv6), by T. Narten et al. (September 2007), as a network element uses IPv6 ND to discover its neighbor's attributes, a neighbor cache (NC) is filled with NC entries, keyed on the neighbor's IPv6 address, containing information such as link-layer address, reachability state, and a time to a next Neighbor Unreachability Detection event.
As a network element generates, or retransmits, packets destined for a neighbor, the network element looks up the destination's IP address in the NC and utilizes a corresponding entry to determine the link-layer address of the destination. However, the network element may lookup an IP address that is not in the NC, which results in a NC miss. In response to a NC miss, the network element broadcasts a neighbor solicitation (NS) message to request the link-layer address of the destination. Many implementations of the IPv6 ND protocol generate an incomplete, or unresolved, NC entry for the destination while waiting for a response from the destination. The maintenance of a NC can be further explained with reference to existing operations in FIG. 1.
FIG. 1 is a flow diagram illustrating prior art operations for handling IPv6 neighbor discovery. In FIG. 1, three network elements are shown as 101, 103, and 104. Network elements 103 and 104 are part of a network 102 while network element 101 exists outside of network 102. Network element 103 is a network element such as a router, or gateway, between network element 101 and network element 104. As such, packets arriving from network element 101 that are destined for network element 104 are relayed by network element 103.
In FIG. 1, network element 104 transmits a Neighbor Solicitation message intended for duplicate address detection (a DAD-NS message) at step 105 that includes a target address (TA) which the network element 104 intends to assign to its interface with network 102. A DAD-NS message is an NS message used to perform duplicate address detection (DAD), and such an NS messages contains a specified (non-zero) target IP address (TA) with an unspecified (zero) source IP address, without the source link-layer address option. It is a broadcast message to other nodes on the network and the specified TA indicates the IP address the network element will be assigning to its interface on that network. Unless the network element receives a neighbor advertisement (NA) message that contains the same TA, indicating another network element is using that address, then the network element may utilize the TA on its interface. In FIG. 1, the TA at step 105 is noted as 2001::234/128 which is common IPv6 address notation starting with 2001, ending with 234, and containing zeros between as indicated by the double colon. After transmitting the DAD-NS message, network element 104 waits a period of time to wait for an NA indicating the TA is being used by another node. This is the DAD timer period 110. Assuming that an NA is not received for the TA, then the network element 104 assigns the address 2001::234/128 to its interface in step 115.
As illustrated in FIG. 1, prior to, during, or after the assigning of the interface address in step 115, a packet arrives at network element 103 destined for the address 2001:234/128 in step 120. In response to receiving the packet and determining that it needs to relay that packet to a network element (i.e., node) on its network, network element 103 checks its NC for an entry matching the address with a corresponding link-layer address. In this instance, the NC does not have this entry as it has not yet been created and thus a NC miss event occurs on address 2001::234/128 at step 125. In response to the NC miss event, network element 103 adds an empty entry, also known as an incomplete entry or unconfirmed entry, into the NC with an IP address of 2001::234/128 in step 130 and broadcasts an NS message with a target address of 2001::234/128 in step 135. Unlike the DAD-NS in 105, this NS contains a target address of 2001::234/128 and a source IP address of the interface belonging to network element 103 in network 102, and also contains a source link-layer address of the interface belonging to network element 103 if the link layer has addresses. In response to the NS message, network element 104, assuming it has already performed step 115, responds with an NA message indicating its target address of 2001::234/128 and its link-layer address, shown as DE:EB:AA:5F:C4:02, in step 140. In response to receiving the NA message from step 140, network element 103 is able to update its NC entry corresponding with the IP address 2001::234/128 to associate the received link-layer address of DE:EB:AA:5F:C4:02 in step 145; thereby, associating the IP address and link-layer address to network element 104. Using this newly discovered association, the network element 103 is able to route the packet received at step 120 to network element 104 using the link-layer address of DE:EB:AA:5F:C4:02 in step 150.
Similarly, FIG. 1 illustrates that a second packet arrives from network element 101 at network element 103 in step 155. This packet is destined for the IP address 2001::285/128. In response to receiving the packet and determining that it needs to relay that packet to a network element on its network, network element 103 checks its NC for an entry matching the IP address with a corresponding link-layer address. In this instance, the NC does not have this entry for address 2001::285/128 and, thus, experiences a NC miss event at step 160. In response to the NC miss event, network element 103 adds an empty entry into the NC with an IP address of 2001::285/128 in step 165 and broadcasts an NS message with a TA of 2001::285/128 in step 170. However, there will be no reply NA message with a TA of 2001::285/128 because there are no network elements with that IP address in network 102.
Thus, as noted by the Internet Draft Mitigating Neighbor Discovery Based Denial of Service Attacks, by J. Halpern (October 2011), there exists a potential that the NC will be filled with incomplete NC entries for many unresolved neighbors. The draft further asks whether NC misses are necessary. If NC misses can be ignored, then an off-link flooding denial of service (DoS) attack that uses NC misses to kill a router can be neutralized. For example, one technique to eliminate the need for NC misses is to, for each resolved neighbor, the IPv6 ND protocol actively monitors the reachability of that neighbor by extending the lifetime of the neighbor entry for that neighbor through periodic NS messages and retains the neighbor entry in the NC for as long as the neighbor entry's lifetime has not expired.
Another potential issue arises when a network element rate limits the NC miss events. In this scenario, many NC miss events may occur but the network element limits the number of acknowledged NC miss events, i.e. limits the number of events to which the network element reacts. As such, the network element may receive legitimate or illegitimate traffic including IP address that are not in the NC. In such a scenario, the network element may react to very few NC miss events to the exclusion of learning the link-layer address of the legitimate traffic.